﻿namespace AdvancedTraining.Lesson49;

/// <summary>
/// LeetCode 377. 组合总和 Ⅳ
/// 给定一个由不同整数组成的数组 nums 和一个目标整数 target，
/// 请你从 nums 中找出并返回总和为 target 的元素组合的个数。
/// </summary>
/// <remarks>
/// 题目注意：
/// 1. 顺序不同的序列被视作不同的组合。
/// 2. nums 中的数字可以无限制重复被选取。
/// 3. 答案需要模 10^9 + 7（在实际LeetCode中）
///
/// 算法思路：
/// 1. 暴力递归：尝试所有可能的组合，时间复杂度O(n^target)
/// 2. 记忆化搜索：缓存递归结果，避免重复计算，时间复杂度O(n*target)
/// 3. 动态规划：严格位置依赖的DP，时间复杂度O(n*target)，空间复杂度O(target)
///
/// 状态定义：dp[i] 表示凑成目标i的组合个数
/// 状态转移：dp[i] = Σ(dp[i - nums[j]]) 其中nums[j] <= i
/// 初始条件：dp[0] = 1（空序列是一种组合）
/// </remarks>
public class CombinationSumIV //leetcode_0377
{
    private static readonly int[] Dp = new int[1001];

    /// <summary>
    /// 暴力递归方法 - 尝试所有可能的组合
    /// 时间复杂度：O(n^target)，会超时
    /// </summary>
    /// <param name="rest">剩余需要凑成的目标值</param>
    /// <param name="numbers">候选数字数组</param>
    /// <returns>组合个数</returns>
    public static int Ways(int rest, int[] numbers)
    {
        if (rest < 0) return 0;
        if (rest == 0) return 1;
        var ways = 0;
        foreach (var num in numbers) ways += Ways(rest - num, numbers);
        return ways;
    }

    /// <summary>
    /// 记忆化搜索方法 - 缓存递归结果避免重复计算
    /// 时间复杂度：O(n*target)
    /// 空间复杂度：O(target)
    /// </summary>
    /// <param name="numbers">候选数字数组</param>
    /// <param name="target">目标值</param>
    /// <returns>组合个数</returns>
    public static int CombinationSum41(int[] numbers, int target)
    {
        Array.Fill(Dp, -1, 0, target + 1);
        return Process1(numbers, target);
    }

    /// <summary>
    /// 记忆化搜索的递归处理函数
    /// </summary>
    /// <param name="numbers">候选数字数组</param>
    /// <param name="rest">剩余需要凑成的目标值</param>
    /// <returns>组合个数</returns>
    private static int Process1(int[] numbers, int rest)
    {
        if (rest < 0) return 0;
        if (Dp[rest] != -1) return Dp[rest];
        var ans = 0;
        if (rest == 0)
            ans = 1;
        else
            foreach (var num in numbers)
                ans += Process1(numbers, rest - num);
        Dp[rest] = ans;
        return ans;
    }

    /// <summary>
    /// 动态规划方法 - 剪枝 + 严格位置依赖的动态规划
    /// 时间复杂度：O(n*target)
    /// 空间复杂度：O(target)
    /// </summary>
    /// <param name="numbers">候选数字数组</param>
    /// <param name="target">目标值</param>
    /// <returns>组合个数</returns>
    public static int CombinationSum42(int[] numbers, int target)
    {
        Array.Sort(numbers);
        var dp = new int[target + 1];
        dp[0] = 1;
        for (var rest = 1; rest <= target; rest++)
        for (var i = 0; i < numbers.Length && numbers[i] <= rest; i++)
            dp[rest] += dp[rest - numbers[i]];
        return dp[target];
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 组合总和 IV 测试 ===");

        // 测试用例1：LeetCode官方示例
        var test1Nums = new[] { 1, 2, 3 };
        var test1Target = 4;
        var result1Ways = Ways(test1Target, test1Nums);
        var result1Mem = CombinationSum41(test1Nums, test1Target);
        var result1Dp = CombinationSum42(test1Nums, test1Target);
        Console.WriteLine($"测试用例1: nums=[{string.Join(", ", test1Nums)}], target={test1Target}");
        Console.WriteLine($"暴力递归结果: {result1Ways}, 记忆化搜索结果: {result1Mem}, 动态规划结果: {result1Dp}");
        Console.WriteLine($"期望: 7, 结果: {(result1Dp == 7 ? "✓ 通过" : "✗ 失败")}");
        Console.WriteLine();

        // 测试用例2：单个数字
        var test2Nums = new[] { 2 };
        var test2Target = 3;
        var result2 = CombinationSum42(test2Nums, test2Target);
        Console.WriteLine($"测试用例2: nums=[{string.Join(", ", test2Nums)}], target={test2Target}");
        Console.WriteLine($"结果: {result2}, 期望: 0");
        Console.WriteLine(result2 == 0 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例3：目标为0
        var test3Nums = new[] { 1, 2, 3 };
        var test3Target = 0;
        var result3 = CombinationSum42(test3Nums, test3Target);
        Console.WriteLine($"测试用例3: nums=[{string.Join(", ", test3Nums)}], target={test3Target}");
        Console.WriteLine($"结果: {result3}, 期望: 1");
        Console.WriteLine(result3 == 1 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例4：较大数字
        var test4Nums = new[] { 2, 3, 5 };
        var test4Target = 8;
        var result4 = CombinationSum42(test4Nums, test4Target);
        Console.WriteLine($"测试用例4: nums=[{string.Join(", ", test4Nums)}], target={test4Target}");
        Console.WriteLine($"结果: {result4}, 期望: 6");
        Console.WriteLine(result4 == 6 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例5：包含1的情况
        var test5Nums = new[] { 1, 3, 4 };
        var test5Target = 4;
        var result5 = CombinationSum42(test5Nums, test5Target);
        Console.WriteLine($"测试用例5: nums=[{string.Join(", ", test5Nums)}], target={test5Target}");
        Console.WriteLine($"结果: {result5}, 期望: 4");
        Console.WriteLine(result5 == 4 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例6：重复数字的组合
        var test6Nums = new[] { 1, 2 };
        var test6Target = 5;
        var result6 = CombinationSum42(test6Nums, test6Target);
        Console.WriteLine($"测试用例6: nums=[{string.Join(", ", test6Nums)}], target={test6Target}");
        Console.WriteLine($"结果: {result6}, 期望: 8");
        Console.WriteLine(result6 == 8 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例7：空数组
        var test7Nums = Array.Empty<int>();
        var test7Target = 5;
        var result7 = CombinationSum42(test7Nums, test7Target);
        Console.WriteLine($"测试用例7: nums=[], target={test7Target}");
        Console.WriteLine($"结果: {result7}, 期望: 0");
        Console.WriteLine(result7 == 0 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例8：算法性能对比
        var test8Nums = new[] { 1, 2, 3 };
        var test8Target = 10;
        Console.WriteLine($"测试用例8: 性能对比测试 nums=[{string.Join(", ", test8Nums)}], target={test8Target}");

        // 暴力递归（仅用于小目标值）
        var start = DateTime.Now;
        var bruteForceResult = Ways(test8Target, test8Nums);
        var bruteForceTime = (DateTime.Now - start).TotalMilliseconds;

        // 记忆化搜索
        start = DateTime.Now;
        var memoizationResult = CombinationSum41(test8Nums, test8Target);
        var memoizationTime = (DateTime.Now - start).TotalMilliseconds;

        // 动态规划
        start = DateTime.Now;
        var dpResult = CombinationSum42(test8Nums, test8Target);
        var dpTime = (DateTime.Now - start).TotalMilliseconds;

        Console.WriteLine($"暴力递归: 结果={bruteForceResult}, 耗时={bruteForceTime:F2}ms");
        Console.WriteLine($"记忆化搜索: 结果={memoizationResult}, 耗时={memoizationTime:F2}ms");
        Console.WriteLine($"动态规划: 结果={dpResult}, 耗时={dpTime:F2}ms");
        Console.WriteLine($"结果一致性: {(bruteForceResult == memoizationResult && memoizationResult == dpResult ? "✓ 一致" : "✗ 不一致")}");
        Console.WriteLine();

        Console.WriteLine("=== 算法说明 ===");
        Console.WriteLine("问题：给定候选数字数组，求凑成目标值的组合个数（顺序不同视为不同组合）");
        Console.WriteLine("暴力递归：时间复杂度O(n^target)，容易超时");
        Console.WriteLine("记忆化搜索：时间复杂度O(n*target)，缓存递归结果");
        Console.WriteLine("动态规划：时间复杂度O(n*target)，空间复杂度O(target)，最优解法");
        Console.WriteLine("状态转移方程：dp[i] = Σ(dp[i - nums[j]]) 其中nums[j] <= i");
    }
}